package dynamicProgramming.knapsack;

/**
 * @author zxc
 * @date 2023/01/26 10:31
 **/
/**
 * 题目 ：加减目标值
 * 题目详述 ：
 * 给定一个正整数数组 nums 和一个整数 target 。
 * 向数组中的每个整数前添加'+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
 * 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
 * 返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
 *
 * 提示：
 * 1 <= nums.length <= 20
 * 0 <= nums[i] <= 1000
 * 0 <= sum(nums[i]) <= 1000
 * -1000 <= target <= 1000
 */
public class FindTargetSumWays02 {
    /**
     * 思路 ：
     * 即，问题转换 :
     * 假设 ：p为所需要累加的数字集合;q为所需要累减的数字集合;sum为所有数组元素和;target为所要求的目标值
     * p + q = sum  && p - q = target
     * ===> 2*p = (sum + target)
     * ===> 即，转换为 在nums数组中寻找累加值等于(sum + target) / 2的数组元素集合;
     *
     * 状态转移方程 ：
     * 假设f(i,j)为在前i个数组元素中选择若干个元素填满容量为j的背包
     * （1）当j == 0（即，背包容量j为0），必然为1（即，nums数组中每个元素都不去进行选择）
     * （2）当i == 0 && j > 0（即，物品数量为0/数组nums == 0）,必然为0（即，不成立）
     * （3）当i > 0 && j > nums[i]时，===》f(i,j) = f(i-1,j) + f(i-1,j-nums[i]);
     *
     * @param nums
     * @param target
     * @return
     */
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 特殊情况1 ：若是数组中元素值之和sum < 目标元素值target的话，即不成立;
        // 特殊情况2 ：若是(sum + target) % 2 == 1,也是不成立的;
        // ===> 即，sum + target为奇数的话，同时又由于背包容量j == (sum + target) / 2;
        if(sum < target || (sum + target) % 2 == 1){
            return 0;
        }
        return findTarget(nums , (sum + target) / 2);
    }

    private int findTarget(int[] nums, int target) {
        // 即，使用一维数组temp[target + 1]来保存计算过程中结果;
        int[] temp = new int[target + 1];
        // （1）temp[06666666666666666666666666666666666[0]，即大小为0的数组中选择若干元素来填满容量为target的背包,其结果必然为1;
        temp[0] = 1;
        // 由于temp[j]一开始保存的是f(i-1,j);
        for(int i = 1; i <= nums.length ; i++){
            // 假设f(i,j)为大小为i的数组中选择若干个填满容量为j的背包的数量;
            // 求取f(i,j)的话，即需要f(i-1,j)和f(i-1,j-nums[i]);
            // 需要注意的是，若是从右向左遍历数组的话，不需要担心（后续数组元素会使用到之前已经使用过 && 被替代过的数组元素）
            /**
             * 由于求取f(i,j)，需要f(i-1,j)和f(i-1,j-nums[i]);
             * ===》 即，只会使用到当前记录的前一行记录的左边记录;
             * 若是从右向左遍历的话，即会使用f(i,j)的结果去覆盖原先temp[j]所存储的f(i-1,j);
             * 需要注意的是，同时不会对于后续的f(i-x,j)求解有任何影响;
             */
            for(int j = target; j >= 0 ; j--){
                // 若是j >= nums[i - 1]的话，则背包容量足够将第i个物品加入到背包中;
                // 反之，j < nums[i -1]的话，则背包容量不足够将第i个物品加入到背包中;
                // ===>（由于f(i,j) == f(i-1,j),temp[j]所存储的应该还是f(i-1,j)）
                if(j >= nums[i - 1]){
                    temp[j] += temp[j - nums[i - 1]];
                }
            }
        }
        return temp[target];
    }
}